#include "Utils.h"
#include "ListNode.h"
#include "TreeNode.h"
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Issue235 {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root==p)
			return p;
		if(root==q)
			return q;
		if((root->val>p->val&&root->val<q->val)||(root->val<p->val&&root->val>q->val))
			return root;
		if(p->val<root->val&&q->val<root->val)
			return lowestCommonAncestor(root->left,p,q);
		else
			return lowestCommonAncestor(root->right,p,q);
	}
};

int main235(){
	Issue235 sol;
	//TreeNode* root=new TreeNode(6);
	//root->left=new TreeNode(2);
	//root->right=new TreeNode(8);
	//root->left->left=new TreeNode(0);
	//root->left->right=new TreeNode(4);
	//root->left->right->left=new TreeNode(3);
	//root->left->right->right=new TreeNode(5);
	//root->right->left=new TreeNode(7);
	//root->right->right=new TreeNode(9);

	int arr[]={6,2,8,0,4,7,9};
	TreeNode* root=arr_to_tree(arr,size(arr));

	TreeNode* p=root->left;
	TreeNode* q=root->left->right;
	
	TreeNode* LCA=sol.lowestCommonAncestor(root,p,q);

	cout<<LCA->val<<endl;
	return 0;
}